#include <iostream>
#include <stdio.h>
#include <vector>
using namespace std;
int coinChange(int amount, int a[]) 
{
  vector<int> coin({1,5,10,25});
  vector<vector<int>> dp(amount+1,vector<int>(coin.size()+1,0));
  for(int i=1;i<amount+1;i++){
    dp[i][0]=amount+1;
    for(int j=0;j<coin.size();j++){
      if((i-coin[j]<0)||dp[i-coin[j]][j+1]>=a[j]) continue;
      if(dp[i][0]>1+dp[i-coin[j]][0]){
	dp[i][0]=1+dp[i-coin[j]][0];
	for(int k=0;k<coin.size();k++){
	  dp[i][k+1]=dp[i-coin[j]][k+1];
	}
	dp[i][j+1]++;
    }
  }
  }
  return (dp[amount][0] == amount+1)? -1: dp[amount][0];
}

  
